/*
 * Copyright (c) 2018-2022, 四川蜀天梦图数据科技有限公司.
 * All rights reserved.
 */

package link_list

//https://leetcode.cn/problems/merge-two-sorted-lists/ leetcode-21

// 迭代
func mergeTwoLists0(list1 *ListNode, list2 *ListNode) *ListNode {
	var result *ListNode
	var tmp *ListNode
	for list1 != nil || list2 != nil {
		var small *ListNode

		if list1 == nil {
			small = list2
			list2 = list2.Next
		} else if list2 == nil {
			small = list1
			list1 = list1.Next
		} else if list1 != nil && list2 != nil {
			if list1.Val < list2.Val {
				small = list1
				list1 = list1.Next
			} else {
				small = list2
				list2 = list2.Next
			}
		}

		if result == nil {
			result = small
			tmp = result
		} else {
			tmp.Next = small
			tmp = tmp.Next
		}
	}

	return result
}

// 递归
func mergeTwoLists1(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	} else if list2 == nil {
		return list1
	} else if list1.Val < list2.Val {
		list1.Next = mergeTwoLists1(list1.Next, list2)
		return list1
	} else {
		list2.Next = mergeTwoLists1(list1, list2.Next)
		return list2
	}
}
